package com.practice.binarysearch;

/**
 * Sorted array with repeated elements for given element, find out its range.
 * e.g. A A B B B B B C C D D E F G, given B, the output should be [2, 6] 
 *
 */
public class RangeSearch {
	public int[] findRange(int[] a, int value) {
		return find(a, value, 0, a.length-1);
	}
	
	private int[] find(int[] a, int target, int low, int high) {
		if (low > high) return new int[]{-1, -1};
		int mid = (low + high) / 2;
		
		if (a[mid] > target) {
			return find(a, target, low, mid-1);
		}
		else if (a[mid] < target) {
			return find(a, target, mid+1, high);
		}
		
		int left = findLeft(a, target, low, mid);
		int right = findRight(a, target, mid, high);
		return new int[]{left, right};
	}
	
	private int findLeft(int[] a, int value, int lower, int upper) {
		int mid = (lower + upper) / 2;
		if (mid == lower) return a[lower]==value? lower : lower+1;
		
		if (a[mid] == value) {
			return findLeft(a, value, lower, mid);
		}
		else {
			return findLeft(a, value, mid, upper);
		}
	}
	
	private int findRight(int[] a, int value, int lower, int upper) {
		int mid = (lower + upper) / 2;
		if (mid == lower) return a[mid+1]==value? mid+1 : mid;
		
		if (a[mid] > value) {
			return findRight(a, value, lower, mid);
		}
		else {
			return findRight(a, value, mid, upper);
		}
	}
}
